The field of computer graphics concerns the creation, storage, manipulation and display of pictures and models of objects by a digital processor. Interactive computer graphics is the subclass of computer graphics in which a user dynamically controls the picture's content, format, size or color on a display surface by means of an interaction device such as a keyboard, lever or joystick. See Fundamentals of Interactive Computer Graphics, by J. D. Foley and A. Van Dam, ISBN: 0-201-14468-9. The creation of synthetic images (i.e., images which exist as abstract collections of lines, points, curves, etc., in the computer's memory) is the usual domain of interactive computer graphics. This is in contrast to the creation of images of real objects, which come directly or indirectly from a scanning device of some sort, e.g., a film scanner, TV scanner, ultrasound scanner, etc.
There are two primary classes of interactive computer graphics systems: random-scan and raster-scan systems. Images displayed by a random-scan system are encoded as commands to draw each output primitive (i.e., point, line or polygon) by plotting individual points or drawing connecting lines between specified starting and ending coordinates of line segments. Polygons are simply treated as a closed series of line segments. Encoding for a raster-scan system is much simpler: output primitives are broken up into their constituent points for display. The major difference between a simple point-plotting random-scan system and a raster-scan system is in the organization of the stored data used to drive the display. (As explained below, the data is stored in a frame buffer or refresh buffer.) In the random-scan display system, the component points of each successive output primitive are stored sequentially in memory and are plotted in that order, one point at a time. This is because the beam may be moved randomly on the screen. In the raster-scan display system, the refresh memory is arranged as a 2-dimensional array of data. The entry or value stored at a particular row and column encodes an intensity and/or color value of a corresponding display element on the screen. By convention, the location of each display element is specified by a unique (X,Y) coordinate. Z conventionally represents the depth ordinate.
Since each memory location defines a single point-sized element of an image, both the display screen location and its corresponding memory location are often called a "pixel," short for the image processing term "picture element." Hereinafter, to avoid confusion, the term "display pixel" is used to indicate picture elements of a display device, and "storage pixel" to indicate memory locations corresponding to the display pixels.
FIG. 1 is a simplified block diagram of a typical raster-scan graphic system. Such a system includes an image creation system 12, an image storage system 14 (such as a refresh buffer or frame buffer), an image display system 16, a raster display 18 and an interaction device 20. The image creation system 12 converts output primitives into the data stored in the refresh buffer or frame buffer of the image storage system 14. The instruction set processing speed of the image creation system 12 establishes most of the characteristics of the raster-scan system 10. Moreover, the image creation system 12 is particularly malleable because it is typically implemented with a microprocessor. See Chapter 12 of Fundamentals of Interactive Computer Graphics, referenced above.
In addition to the basic components enumerated above, there may also be a Z-interpolator for interpolating Z ordinate values (or Z values) of points along a line having a nonconstant depth, e.g., a segment of a three dimensional surface. As explained more fully below, a problem with known Z-interpolators is that they often lack sufficient precision to accurately determine which of two or more overlapping images to display. If the computed depth of a line is in error, a line that should not be displayed (a "hidden line") may be displayed, and a line that should be displayed may not. This hidden line problem is aggravated when the slope of one or more of the lines defining the surface becomes extremely large. The problem can be mitigated for large slopes by making the hardware (i.e., divider) used to compute the Z values more elaborate, but only at a significantly greater cost. Accordingly, an object of the present invention is to provide a method and corresponding apparatus for precisely interpolating Z ordinate values of lines to be displayed. A further object of the present invention is to provide such a method and apparatus while also ensuring that the divider used to calculate slope does not overflow when the slope becomes very large. The present invention achieves these goals.